package com.ly.algorithm.offerpointer;

import jdk.management.resource.internal.ApproverGroup;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @Classname Offer40
 * @Description
 *
 * 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：arr = [3,2,1], k = 2
 * 输出：[1,2] 或者 [2,1]
 * 示例 2：
 *
 * 输入：arr = [0,1,2,1], k = 1
 * 输出：[0]
 *
 *
 * @Date 2021/1/30 16:34
 * @Author 冷心影翼
 */
public class Offer40 {

    public static void main(String[] args) {
        Solution40 solution40 = new Solution40();
        int[] leastNumbers = solution40.getLeastNumbers(new int[]{0,11,34,55,77,23}, 3);
        int[] leastNumbers2 = solution40.getLeastNumbers2(new int[]{0,11,34,55,77,23}, 3);
        int[] leastNumbers3 = solution40.getLeastNumbers3(new int[]{0,11,212,222,-5,34,55,77,23}, 3);
        System.out.println(Arrays.toString(leastNumbers));
        System.out.println(Arrays.toString(leastNumbers2));
        System.out.println(Arrays.toString(leastNumbers3));
    }
    
}


class Solution40 {
    public int[] getLeastNumbers(int[] arr, int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for (int i = 0; i < arr.length; i++) {
            priorityQueue.add(arr[i]);
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = priorityQueue.poll();
        }
        return res;
    }

    public int[] getLeastNumbers2(int[] arr, int k) {
        for (int i = arr.length/2; i >= 0; i--) {
            adjust(arr,i,arr.length);
        }
        int[] res = new int[k];
        for (int i = arr.length-1; i >= 0; i--) {
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            adjust(arr,0,i);
        }
        for (int i = 0; i < k; i++) {
            res[i] = arr[i];
        }
        return res;
    }


    private void adjust(int[] arr,int i,int heapSize) {
        int l = i*2+1;
        int r = i*2+2;
        int max = i;
        if(l<heapSize && arr[l] > arr[max]) {
            max = l;
        }
        if(r<heapSize && arr[r] > arr[max]) {
            max = r;
        }
        if(max != i) {
            int temp = arr[max];
            arr[max] = arr[i];
            arr[i] = temp;
            adjust(arr,max,heapSize);
        }
    }


    public int[] getLeastNumbers3(int[] arr, int k) {
        select(arr,0,arr.length-1,k);
        return arr;
    }

    private void select(int[] arr, int left,int right,int k) {
        int m = quickSort(arr, left, right);
        if(m == k) {
            return;
        }else if( k<m ) {
            select(arr,left,m-1,k);
        }else {
            select(arr,m+1,right,k);
        }
    }


    private int quickSort(int[] arr, int left, int right) {
        int p = arr[left];
        int i = left;
        int j = right;
        while (i<j) {
            while (i<j && arr[j]>=p) {
                j--;
            }
            arr[i] = arr[j];
            while (i<j && arr[i]<p) {
                i++;
            }
            arr[j] = arr[i];
        }
        arr[i] = p;
        return  j;

    }

}